static const char* prefixScanKernelsCL= \
"/*\n"
"		2011 Takahiro Harada\n"
"*/\n"
"\n"
"typedef unsigned int u32;\n"
"#define GET_GROUP_IDX get_group_id(0)\n"
"#define GET_LOCAL_IDX get_local_id(0)\n"
"#define GET_GLOBAL_IDX get_global_id(0)\n"
"#define GET_GROUP_SIZE get_local_size(0)\n"
"#define GROUP_LDS_BARRIER barrier(CLK_LOCAL_MEM_FENCE)\n"
"\n"
"// takahiro end\n"
"#define WG_SIZE 128\n"
"\n"
"typedef struct\n"
"{\n"
"	uint m_numElems;\n"
"	uint m_numBlocks;\n"
"	uint m_numScanBlocks;\n"
"	uint m_padding[1];\n"
"} ConstBuffer;\n"
"\n"
"\n"
"u32 ScanExclusive(__local u32* data, u32 n, int lIdx, int lSize)\n"
"{\n"
"	u32 blocksum;\n"
"    int offset = 1;\n"
"    for(int nActive=n>>1; nActive>0; nActive>>=1, offset<<=1)\n"
"    {\n"
"        GROUP_LDS_BARRIER;\n"
"        for(int iIdx=lIdx; iIdx<nActive; iIdx+=lSize)\n"
"        {\n"
"            int ai = offset*(2*iIdx+1)-1;\n"
"            int bi = offset*(2*iIdx+2)-1;\n"
"            data[bi] += data[ai];\n"
"        }\n"
"	}\n"
"\n"
"    GROUP_LDS_BARRIER;\n"
"\n"
"    if( lIdx == 0 )\n"
"	{\n"
"		blocksum = data[ n-1 ];\n"
"        data[ n-1 ] = 0;\n"
"	}\n"
"\n"
"	GROUP_LDS_BARRIER;\n"
"\n"
"	offset >>= 1;\n"
"    for(int nActive=1; nActive<n; nActive<<=1, offset>>=1 )\n"
"    {\n"
"        GROUP_LDS_BARRIER;\n"
"        for( int iIdx = lIdx; iIdx<nActive; iIdx += lSize )\n"
"        {\n"
"            int ai = offset*(2*iIdx+1)-1;\n"
"            int bi = offset*(2*iIdx+2)-1;\n"
"            u32 temp = data[ai];\n"
"            data[ai] = data[bi];\n"
"            data[bi] += temp;\n"
"        }\n"
"	}\n"
"	GROUP_LDS_BARRIER;\n"
"\n"
"	return blocksum;\n"
"}\n"
"\n"
"\n"
"__attribute__((reqd_work_group_size(WG_SIZE,1,1)))\n"
"__kernel\n"
"void LocalScanKernel(__global u32* dst, __global u32 *src, __global u32 *sumBuffer,\n"
"		ConstBuffer cb)\n"
"{\n"
"	__local u32 ldsData[WG_SIZE*2];\n"
"\n"
"	int gIdx = GET_GLOBAL_IDX;\n"
"	int lIdx = GET_LOCAL_IDX;\n"
"\n"
"	ldsData[2*lIdx]     = ( 2*gIdx < cb.m_numElems )? src[2*gIdx]: 0;\n"
"	ldsData[2*lIdx + 1] = ( 2*gIdx+1 < cb.m_numElems )? src[2*gIdx + 1]: 0;\n"
"\n"
"	u32 sum = ScanExclusive(ldsData, WG_SIZE*2, GET_LOCAL_IDX, GET_GROUP_SIZE);\n"
"\n"
"	if( lIdx == 0 ) sumBuffer[GET_GROUP_IDX] = sum;\n"
"\n"
"	if( (2*gIdx) < cb.m_numElems )\n"
"    {\n"
"        dst[2*gIdx]     = ldsData[2*lIdx];\n"
"	}\n"
"	if( (2*gIdx + 1) < cb.m_numElems )\n"
"	{\n"
"        dst[2*gIdx + 1] = ldsData[2*lIdx + 1];\n"
"    }\n"
"}\n"
"\n"
"__attribute__((reqd_work_group_size(WG_SIZE,1,1)))\n"
"__kernel\n"
"void AddOffsetKernel(__global u32 *dst, __global u32 *blockSum, ConstBuffer cb)\n"
"{\n"
"	const u32 blockSize = WG_SIZE*2;\n"
"\n"
"	int myIdx = GET_GROUP_IDX+1;\n"
"	int lIdx = GET_LOCAL_IDX;\n"
"\n"
"	u32 iBlockSum = blockSum[myIdx];\n"
"\n"
"	int endValue = min((myIdx+1)*(blockSize), cb.m_numElems);\n"
"	for(int i=myIdx*blockSize+lIdx; i<endValue; i+=GET_GROUP_SIZE)\n"
"	{\n"
"		dst[i] += iBlockSum;\n"
"	}\n"
"}\n"
"\n"
"\n"
"__attribute__((reqd_work_group_size(WG_SIZE,1,1)))\n"
"__kernel\n"
"void TopLevelScanKernel(__global u32* dst, ConstBuffer cb)\n"
"{\n"
"	__local u32 ldsData[2048];\n"
"	int gIdx = GET_GLOBAL_IDX;\n"
"	int lIdx = GET_LOCAL_IDX;\n"
"	int lSize = GET_GROUP_SIZE;\n"
"\n"
"	for(int i=lIdx; i<cb.m_numScanBlocks; i+=lSize )\n"
"	{\n"
"		ldsData[i] = (i<cb.m_numBlocks)? dst[i]:0;\n"
"	}\n"
"\n"
"	GROUP_LDS_BARRIER;\n"
"\n"
"	u32 sum = ScanExclusive(ldsData, cb.m_numScanBlocks, GET_LOCAL_IDX, GET_GROUP_SIZE);\n"
"\n"
"	for(int i=lIdx; i<cb.m_numBlocks; i+=lSize )\n"
"	{\n"
"		dst[i] = ldsData[i];\n"
"	}\n"
"\n"
"	if( gIdx == 0 )\n"
"	{\n"
"		dst[cb.m_numBlocks] = sum;\n"
"	}\n"
"}\n"
;
